package a_简单;

import leetcode.editor.cn.level.简单;
import 分类.双指针;

import java.util.Arrays;

/**
 * @author caihe
 * @date 2023/5/4 14:15
 */
public class _977_有序数组的平方 implements 简单, 双指针 {

    public static void main(String[] args) {
        _977_有序数组的平方 a = new _977_有序数组的平方();
        a.sortedSquares_double_pointer(new int[]{-5,-3,-2,-1});
        a.sortedSquares(new int[]{-5,-3,-2,-1});

    }

    public int[] sortedSquares(int[] nums) {
        int right = nums.length - 1;
        int left = 0;
        int[] result = new int[nums.length];
        int index = result.length - 1;
        while (left <= right) {
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                // 正数的相对位置是不变的， 需要调整的是负数平方后的相对位置
                result[index--] = nums[left] * nums[left];
                ++left;
            } else {
                result[index--] = nums[right] * nums[right];
                --right;
            }
        }
        return result;
    }

    public int[] sortedSquares_Violence(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] * nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }

    /**
     * 因为nums是一个升序的数组，但是数组中可能存在负数
     * 负数在平方后存在大于正数平方后的情况
     * 所以可以使用双指针，leftIndex用来指向可能存在负数的最小值
     * rightIndex用来指向最大值，分别进行平方后比较大小
     * 用一个数组保存大的值，并且指针移动
     */
    public int[] sortedSquares_double_pointer(int[] nums) {
        int left = 0, right = nums.length - 1;
        int[] res = new int[nums.length];
        int index = right;
        while(left <= right) {
            int leftNum = nums[left] * nums[left];
            int rightNum = nums[right] * nums[right];
            if (leftNum > rightNum) {
                res[index--] = leftNum;
                left++;
            } else {
                res[index--] = rightNum;
                right--;
            }
        }
        return res;
    }

}
